#ifndef QUADTREE_H
#define QUADTREE_H

#include <QList>
#include <QPoint>

#define QUAD_TREE_SPLIT_SIZE 10

class Entity;
class QuadTree
{
  public:
    QuadTree(const QList<Entity*>& entities, const QPoint& center, float length, float height, int splitSize = QUAD_TREE_SPLIT_SIZE);
    ~QuadTree();

    void build(const QList<Entity*>& entities, const QPoint& center, float length, float height, int splitSize);
    void addEntities(const QList<Entity*>& entities);
    void addEntity(Entity* entity);
    QList<Entity*> getEntitiesInRadius(const QPoint& position, int range);
    void getEntitiesInRadius(const QPoint& position, int range, QList<Entity*>& container);

  protected:
    class QuadTreeNode;
    QList<Entity*> mEntities;
    QuadTreeNode *mRoot;
};

class QuadTree::QuadTreeNode
{
  public:
    QuadTreeNode(const QPoint& center, float length, float height, int splitSize, QuadTreeNode *parent = NULL);
    QuadTreeNode(const QList<Entity*>& entities, const QPoint& center, float length, float height, int splitSize, QuadTreeNode *parent = NULL);

    void addEntities(const QList<Entity*>& entities);
    void addEntity(Entity* entity);
    void getEntitiesInRadius(const QPoint& position, int range, QList<Entity*>& container);
    bool isInRange(const QPoint& position, int range) const;
    bool wouldContain(const QPoint& position) const;

  protected:
    void split();
    void merge();
    int getNumContainingEntities() const;

    QuadTreeNode *mParent,
                 *mTopLeftChild, *mTopRightChild,
                 *mBottomLeftChild, *mBottomRightChild;
    float mLength, mHeight;
    int mSplitSize;
    bool mIsSplit;
    QPoint mCenter,
           mTopLeftPosition, mTopRightPosition,
           mBottomLeftPosition, mBottomRightPosition;
    QList<Entity*> mEntities;

};

#endif // QUADTREE_H
